显然，题目求的是：
SP694 DISUBSTR - Distinct Substrings
这道题用后缀自动机可以暴力解决。
建好后缀自动机后 , 因为起点到后缀自动机上的每一个点都是一个本质不同的子串 ， 我们就可以在 DAWG 上 dp 。 dp[u]表示包含转移u的子串数量，很容易列出转移式：
SP1811 LCS - Longest Common Substring
一道后缀自动机的板题。
我们从根结点开始匹配，如果有转移就将cnt++
不然就顺着后缀链接向上跳，直到找到有转移的点，用 Maxlen 继续匹配。(后缀链接一定是它的子串，也能被匹配)。
P2408 不同子串个数
这道题用后缀自动机可以暴力解决。
建好后缀自动机后 , 因为起点到后缀自动机上的每一个点都是一个本质不同的子串 ， 我们就可以在 DAWG 上 dp 。 dp[u]表示包含转移u的子串数量，很容易列出转移式：
SP8222 NSUBSTR - Substrings
不难发现到f[i]就是长度为 i 子串的 ∣endpos∣ 的最大值。
根据一个性质后缀自动机的一个点的 endpos 被他的后继分为了很多部分，所以我们可以用parent树dp，处理出它的∣endpos∣。
接着是统计答案，显然我们可以用线段树覆盖。
P3195 [HNOI2008]玩具装箱TOY
这道题像我这样的 dp 蒟蒻都能一眼看出 dp 式：
设 sum 为 c 的前缀和，则有
CF321E Ciel and Gondolas
各位大佬都用的 wqs 二分，蒟蒻介绍一种简单方法。
dp 式很好列:
0%
